package leetcode_1101_1200;

import java.util.*;

public class LeeCode_1106 {
    public static void main(String[] args) {
        System.out.println(parseBoolExpr("&(|(f))"));
    }
    private static boolean parseBoolExpr(String expression) {
        int n = expression.length();
        Deque<Character> deque = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            char c = expression.charAt(i);
            if (c == ',')
                continue;
            if (c != ')'){
                deque.push(c);
            }else {
                int t = 0, f = 0;
                while (deque.peek() != '('){
                    Character p = deque.pop();
                    if (p == 't')
                        t++;
                    else
                        f++;
                }
                deque.pop();
                Character po = deque.pop();
                switch (po){
                    case '&':
                        deque.push(f == 0 ? 't' : 'f');
                        break;
                    case '|':
                        deque.push(t > 0 ? 't' : 'f');
                        break;
                    case '!':
                        deque.push(f == 1 ? 't' : 'f');
                        break;
                    default:
                }
            }
        }
        return deque.pop() == 't';
    }
}